A set of $N$ permutations of $\{1,2,\dots,v\}$ is $(N,v,t)$-suitable if eachsymbol precedes each subset of $t-1$ others in at least one permutation. Thecentral problems are to determine the smallest $N$ for which such a set existsfor given $v$ and $t$, and to determine the largest $v$ for which such a setexists for given $N$ and $t$. These extremal problems were the subject ofclassical studies by Dushnik in 1950 and Spencer in 1971. We give examples ofsuitable sets of permutations for new parameter triples $(N,v,t)$. We relatecertain suitable sets of permutations with parameter $t$ to others withparameter $t+1$, thereby showing that one of the two infinite families recentlypresented by Colbourn can be constructed directly from the other. We prove anexact nonexistence result for suitable sets of permutations using elementarycombinatorial arguments. We then establish an asymptotic nonexistence resultusing Ramsey's theorem.
展开▼
机译：一组$ \ {1,2，\ dots，v \} $的$ N $排列为$（N，v，t）$-如果每个符号在至少一个$ t-1 $其他子集之前位于每个符号之前排列。中心问题是确定给定$ v $和$ t $时存在这样的集合的最小$ N $，并确定给定$ N $和$ t $时存在这样的集合的最大$ v $。这些极端问题是Dushnik在1950年和Spencer在1971年进行的经典研究的主题。我们给出了新参数三元组（N，v，t）$的适当排列集的示例。我们将参数为$ t $的某些合适的排列集与参数为$ t + 1 $的其他排列相关联，从而表明由Colbourn表示的两个无限家族中的一个可以直接从另一个构造。我们使用基本组合参数证明了合适的排列集的不精确结果。然后，我们使用拉姆西定理建立一个渐近不存在的结果。
展开▼
